package org.wj.problem

import scala.collection.mutable

object InorderTraversal {

  def main(args: Array[String]): Unit = {

  }

  def inorderTraversal(root: TreeNode): List[Int] = {
    if (root == null) Nil else
      inorderTraversal(root.left) ::: List(root.value) ::: inorderTraversal(root.right)
  }

  def inorderTraversal2(root:TreeNode): List[Int] = {
    var varRoot = root
    val stack = new mutable.ArrayStack[TreeNode]
    var list = List[Int]()
    do{
      while(varRoot!=null){
        stack.push(varRoot)
        varRoot = varRoot.left
      }
      if(stack.nonEmpty){
        varRoot = stack.pop()
        list = list :+ varRoot.value
        varRoot = varRoot.right
      }
    }while(stack.nonEmpty || varRoot !=null)
    list
  }



  class TreeNode(var _value: Int) {
    var value: Int = _value
    var left: TreeNode = _
    var right: TreeNode = _

    def value(int: Int): Unit = value = int
  }

}
